The certification path validation algorithm is the algorithm which verifies that a given certificate path is valid under a given public key infrastructure (PKI). A path starts with the Subject certificate and proceeds through a number of intermediate certificates up to a trusted root certificate, typically issued by a trusted Certification Authority (CA).
Path validation is necessary for a relying party to make an informed trust decision when presented with any certificate that is not already explicitly trusted. For example, in a hierarchical PKI, a certificate chain starting with a web server certificate might lead to a small CA, then to an intermediate CA, then to a large CA whose trust anchor is present in the relying party's web browser. In a bridged PKI, a certificate chain starting with a user at Company A might lead to Company A's CA certificate, then to a bridge CA, then to company B's CA certificate, then to company B's trust anchor, which a relying party at company B could trust.
RFC 3280 [1] defines a standardized path validation algorithm for X.509 certificates, given a certificate path. (Path discovery, the actual construction of a path, is not covered.) The algorithm takes the following inputs:
In the standardized algorithm, the following steps are performed for each certificate in the path, starting from the trust anchor. If any check fails on any certificate, the algorithm terminates and path validation fails. (This is an explanatory summary of the scope of the algorithm, not a rigorous reproduction of the detailed steps.)
If this procedure reaches the last certificate in the chain, with no name constraint or policy violations or any other error condition, then the certificate path validation algorithm terminates successfully.